package algorithm.String;

import java.util.Arrays;

public class KMP {
    public static void main(String[] args) {
        String destStr = "BABABACABABCABAABD";
        String subStr ="ABABCABAAB";
        int [] next = getNextPlus(subStr);
        System.out.println(Arrays.toString(next));
        int index = KMPSearch(destStr, subStr);
        System.out.println(index);
    }

    /**
     * 获取next数组
     * @param subStr 模式串
     * @return        next数组
     */
    public static int[] getNext(String subStr){
        //定义一个next数组存放
        int [] next = new int[subStr.length()];
        next[0]=-1;//定义第一个元素是-1
        //定义y为数组下标，len为最长匹配前后缀
        int y = 0,len = -1;
        while (y < subStr.length()-1){
            //如果len和y指向模式串的字符相等那么就是前最长前后缀加1
            if (len == -1 || subStr.charAt(y) == subStr.charAt(len)) {
                y++;
                len++;
                next[y] = len;
            }else {
                //如果y和len指向不相等，就开始回溯到之前最长前后缀尾部比较字符
                len = next[len];
            }
        }
        return next;
    }

    /**
     * KMP的优化算法，假设x与y指针指向字符不同且y指针与len指针指向字符相同，那么就没必要先回溯到next[y],直接令
     * next[y]=next[len],直接回溯到len指针
     * @param subStr  模式串
     * @return        next数组
     */
    public static int[] getNextPlus(String subStr){
        //定义一个next数组存放
        int [] next = new int[subStr.length()];
        next[0]=-1;//定义第一个元素是-1
        //定义y为数组下标，len为最长匹配前后缀
        int y = 0,len = -1;
        while (y < subStr.length()-1){
            //如果len和y指向模式串的字符相等那么就是前最长前后缀加1
            if (len == -1 || subStr.charAt(y) == subStr.charAt(len)) {
//                简化代码在执行判断的时候再自增
//                y++;
//                len++;
                if(subStr.charAt(++len)==subStr.charAt(++y)){
//                  判断y指针和len指针指向字符是否相等，若相等就直接让next[y]=next[len]
                    next[y] = next[len];
                }else {
                    next[y] = len;
                }
            }else {
                //如果y和len指向不相等，就开始回溯到之前最长前后缀尾部比较字符
                len = next[len];
            }
        }
        return next;
    }
    /**
     *
     * @param decStr  主串
     * @param subStr  模式串
     * @return        下标返回（-1为不存在）
     */
    public static int KMPSearch(String destStr,String subStr){
        //获取next数组
        int [] next = getNext(subStr);
        //x指向主串
        int x = 0;
        //y指向模式串
        int y = 0;
        //开始循环，双指针都小于字符串长度
        while(x<destStr.length()&&y<subStr.length()) {
            //如果指针指向主串和模式串的字符相等，就++，还有y=-1时，就是如果第一个字符就不匹配
            if (y==-1||destStr.charAt(x)==subStr.charAt(y)){
                x++;
                y++;
            }else{
                //使用next数组进行查找回溯
                y = next[y];
            }
        }
        //如果y等于leng，就表示已经比对完毕
        if(y==subStr.length()){
            return x-y;
        }else {
            return -1;
        }
    }
}
